package sg.edu.nus.comp.qa.calculator;

public class StringDistanceCalculator implements Calculator {
	private int[][] memory;
	private String a, b;

	@Override
	public double calculate(String a, String b) {
		initializeMemory(a.length(), b.length());
		this.a = a.toLowerCase();
		this.b = b.toLowerCase();
		return doCalculate(0, 0);
	}

	public int doCalculate(int indexA, int indexB) {
		int cost = 0;
		if (indexA == a.length()) {
			return b.length() - indexB;
		} else if (indexB == b.length()) {
			return a.length() - indexA;
		} else {
			if (memory[indexA][indexB] >= 0)
				return memory[indexA][indexB];
			if (a.charAt(indexA) != b.charAt(indexB))
				cost = 1;
			int distance = Math.min(
					Math.min(doCalculate(indexA + 1, indexB) + 1,
							doCalculate(indexA, indexB + 1)),
					doCalculate(indexA + 1, indexB + 1) + cost);
			memory[indexA][indexB] = distance;
			return distance;
		}
	}

	private void initializeMemory(int sizeA, int sizeB) {
		memory = new int[sizeA][sizeB];
		for (int i = 0; i < sizeA; i++)
			for (int j = 0; j < sizeB; j++)
				memory[i][j] = -1;
	}
}
